/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM62 斐波那契数列
 * <a href="https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=295&tqId=23255&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-04
 * Time: 13:21
 */
public class Solution {
    /**
     * 方法一  ----  递归
     * 时间复杂度过高,不建议采用
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        if (n <= 2) {
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
    /**
     * 方法二  ---- 动态规划
     */
    public int Fibonacci2(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] fib = new int[n + 1];
        fib[1] = 1;
        fib[2] = 1;
        for (int i = 3; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }
    /**
     * 方法三  ---- 动态规划改进版
     * 空间复杂度为: O(1)
     */
    public int Fibonacci3(int n) {
        if (n <= 2) {
            return 1;
        }
        int temp1 = 1;
        int temp2 = 1;
        for (int i = 3; i <= n; i++) {
            int temp = temp1 + temp2;
            temp2 = temp1;
            temp1 = temp;
        }
        return temp1;
    }
}
